package com.xxwy.segmenttree.practice.leetcode;

/**
 * @author xxwy
 */
public class NumArray307Second {
    private int[] tree;
    private int[] data;

    public NumArray307Second(int[] nums) {
        data = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            data[i] = nums[i];
        }
        if(nums.length != 0) {
            tree = new int[4 * nums.length];
            builderTree(0, 0, nums.length - 1);
        }
    }

    private void builderTree( int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        int mid = l + (r - l) / 2;
        int left = treeIndex * 2 + 1;
        int right = treeIndex * 2 + 2;
        builderTree(left, l, mid);
        builderTree(right, mid + 1, r);
        tree[treeIndex] = tree[left] + tree[right];
    }

    public int sumRange(int queryL, int queryR) {
        if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
            throw new IllegalArgumentException("Index is illegal");
        }
        return sumRange(0, 0, data.length - 1, queryL, queryR);
    }

    private int sumRange(int treeIndex, int l, int r, int quentL, int quentR) {
        if (quentL == l && quentR == r) {
            return tree[treeIndex];
        }
        int mid = l + (r - l) / 2;
        int left = treeIndex * 2 + 1;
        int right = treeIndex * 2 + 2;
        if (quentR <= mid) {
            return sumRange(left, l, mid, quentL, quentR);
        } else if (quentL >= mid + 1) {
            return sumRange(right, mid + 1, r, quentL, quentR);
        } else {
            int i = sumRange(left, l, mid, quentL, mid);
            int j = sumRange(right, mid + 1, r, mid + 1, quentR);
            return i + j;
        }
    }

    public void update(int index, int val) {
        if(index < 0 || index >=data.length){
            throw new IllegalArgumentException("index is illegal");
        }
        update(0,0,data.length-1,index,val);
    }

    private void update(int treeIndex, int l, int r, int index, int val) {
        if(l==r){
            tree[treeIndex] = val;
            return;
        }
        int mid =l + (r-l)/2;
        int left = treeIndex*2+1;
        int right = treeIndex*2+2;
        if(index >= mid+1){
            update(right,mid+1,r,index,val);
        }else {
            update(left,l,mid,index,val);
        }
        tree[treeIndex] = tree[left] + tree[right];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{};
        NumArray numArray = new NumArray(arr);

    }
}
